ε Del algoritmo al assembler ε -------------------------- Con este título tan sugerente vamos a inciar nuestro viaje por la optimiza- ción y el assembler de hoy. Vamos a tratar de ver las distintas etapas de la creación de una rutina cualquiera optimizada al máximo y prototipada para un lenguaje de alto nivel. En nuestro caso la rutina será un procedimiento para dibujar triangulos rellenos de color en Pascal. Como a muchos no les interesará como se hace, sino que es lo que se consigue y a que velocidad, daré ahora mismo los datos técnicos más importantes de la rutina en su versión final. Mide tan sólo 567 bytes y puede ser llamada desde cualquier versión de Turbo Pascal (no seria difícil de adaptar para otros compiladores). En cuanto a velocidad, es capaz de dibujar unos 8,629,989 pixels por segundo (dibujando triangulos, claro). Dibujando grandes triangulos (de 32000 pixels, media pantalla!) hace unos 270 por segundo, mientras con pequeños triangulos, que suele ser lo importante, hace unos 9090 triangulos de un área de 1200 pixels por segundo, lo cual supondria que con 54 triangulos como este llenariamos la pantalla y conseguiriamos así 168 frames por segundo!! φ El algorimo El primer paso que debemos realizar es pensar como vamos a hacer el algoritmo para dibujar los triangulos sin tener, por ahora, en cuenta como lo implementa- remos. Este es el paso más delicado de todo el proceso, la optimización del có- digo final en assembler está muy bien, pero si no conseguimos un buen algoritmo no nos servirá para nada. Supongo que el algoritmo que desarrollé cuando Skynet me dijo que no tenia en GRAPH 2.0 una rutina para dibujar triangulos para el curso de 3D será el más rápido que exista, aunque puede ser que no, en cuyo caso agradeceria que me lo comunicaras pues en la próxima versión de GRAPH incluiré una de estas rutinas. El algoritmo en cuestión es sencillo de comprender, aunque un poco enrevesado de implementar. Consiste en observar varios triangulos y darte cuenta que en el fondo sólo hay 2 tipos distintos: los que tienen el lado más largo a la derecha de los más cortos y los que lo tienen a la izquierda. Con un poco de matemáti- cas geométricas se podria demostrar esto, pero es tan obvio que no lo creo ne- cesario (que perro!! :). Puedes observar estos 2 tipos en la figura 1. ¿Y que soluciona todo esto? Pues mucho, la verdad. Primeramente nos podemos abstraer a sólo 2 tipos de problemas, cosa muy interesante para no ocupar mucho espacio con la rutina. Además la abstracción que hemos encontrado es simétrica con lo que el problema se simplifica bastante. De lo que se trata es de ir recorriendo el lado largo pintando líneas horizon- tales que son las más rápidas de dibujar. En el primer engendro del algoritmo, escrito en Turbo Pascal (fichero 'φTRIAN.PASπ') podeis observar que se precal- culan algunos valores principalmente para no entrar en el bucle teniendo que calcular todos los valores dentro (se relentizaria muchísimo). Tambien se observa un detalle del algoritmo que no habia mencionado y que es de vital importancia: la subdivisión del problema. No va ha haber un único bucle, sino que habrá dos para simplificar muchísimo el algoritmo; en el primero se dibujará el sub-triangulo de arriba y en el segundo se hará lo propio con el de abajo. El triangulos lo dividiremos en 2 partes que tendrán un lado en común paralelo al borde de la pantalla (de arriba) y que coincidirá con el punto que está al medio (en un triangulo con lados no alineados, siempre habrá un punto central y otros dos que estarán más arriba o más abajo). Los cálculos para los 2 sub-triangulos, por lo general, seran distintos y es por eso por lo que dividimos en 2 el bucle. Como tenemos que saber cual es el punto central, cual el que está arriba y cual el de abajo, los mejor es ordenar- los al principio del todo. Tenemos que calcular las pendientes para la recta más larga (que se mantiene en los 2 bucles) y para cada una de las cortas. Lla- maremos m1 a la larga y m2 a la corta ya que no necesitamos las 2 cortas a la vez (porque hemos dividido el bucle en 2 partes, veis las ventajas). En el bu- cle lo único que tendremos que hacer es incrementar las variables Cx1, Cx2 y Cy1 que determinan la posición. El algoritmo quedaria algo como esto: Γ Algoritmo Triangulo Γ Cx1 <- X1; Cy1 <- Y1; Cx2 <- X1 Γ m1 <- (X1 - X3) / (Y1 - Y3) Γ m2 <- (X1 - X2) / (Y1 - Y2) Ω // Comprobar hacia donde se orienta el triangulo (izquierda o derecha) Γ mientras Cy1<Y2 Ω // Dibujar línea en (Cx1,Cy1) con un tamaño de Cx2-Cx1 pixels Γ Cx1 <- Cx1 + m1 Γ Cx2 <- Cx2 + m2 Γ Cy1 <- Cy1 + 1 Γ fin_mientras Γ m2 <- (X2 - X3) / (Y2 - Y3) Γ mientras Cy1<=Y2 Ω // Dibujar línea en (Cx1,Cy1) con un tamaño de Cx2-Cx1 pixels Γ Cx1 <- Cx1 + m1 Γ Cx2 <- Cx2 + m2 Γ Cy1 <- Cy1 + 1 Γ fin_mientras Γ fin_algoritmo La variable 'com' que aparece en el listado en Pascal, se refiere al tipo del movimiento que calcula según sea el triangulo de izquierda o de derecha y que se debe pasar a la función que dibuja la linea. φ La implementación De la implementación ya hemos comenzado ha hablar un poco en la parte ante- rior así que trataré de no repetirme. El programa 'δTRIAN2.PASπ' no es más que una especie de preparación para el paso a ensamblador que es el lenguaje en el que se Programa. En este módulo de lo que he tratado es de "emular" el ensam- blador pero dentro del Pascal usando variables para contener los registros y teniendo en cuenta en qué registro llevaré cada cosa. A parte de esto, en en- samblador optimizado, no me puedo permitir el lujo de usar el coprocesador ma- temático para los cálculos en punto flotante, así que tendré que usar la coma fija. Supongo y espero que todos conozcais como funciona este método ya que no es este el lugar ni el momento de explicarlo (siempre podeis enviarme un mail y os lo explicaria). Pasando ya de este fichero fuente que por lo general no se programa nunca (salvo con fines ilustrativos como es el caso), vamos con la primera toma de contacto con el Turbo Assembler. El fichero 'δTRIAN3.ASMπ' es la primera versión que nos sale directamente del código fuente en Pascal y que no tiene complica- ción alguna para quienes dominen el assembler y hayan podido seguir los ante- riores fuentes. La función principal es 'δFillTriangleπ', la cual usa intensiva- mente las instrucciones del 386 para mejorar la precisión y la velocidad en los cálculos en punto fijo 25:7. Solo un comentario más sobre esta función, el pro- blema de dibujar la línea horizontal hacia la derecha o la izquierda se ha re- suelto muy facilmente ya que como sabreis las instrucciones REP STOSB pueden tanto incrementar como decrementar DI según el estado del flag de direcciones (lo cambiamos con CLD y STD); para ir a la derecha incrementamos DI y para ir a la izquierda lo decrementamos. En este fuente podemos ver la precisión del dibujado de triangulos ya que en el programa principal lo que se hace es dibujar cada triangulo con la fun- ción 'δFillTriangleπ' para luego "repasar" con líneas ese triangulo. A parte, tambien podemos insertar un contador de tiempo para controlar la velocidad que consigue en este punto y sin optimizar la rutinas principal. (Las pruebas de velocidad en este punto dan aproximadamente unos 1500 triangulos por segundo en un 486DX 50Mhz). φ La optimización La parte de la optimización comienza en el fichero 'δTRIAN4.ASMπ'. Podemos ver que no ha cambiado mucho a excepción de un par de cosas que haran que augmente su velocidad hasta en un 400%. Pero, sin embargo, lo primero que vemos no es una mejor cuantitativa, sino una cualitativa, :) se trata de una corrección de errores no producidos pero posibles fuentes de error: las divisiones por cero. Como para calcular la pendiente de las rectas necesitamos restar 2 terminos y dividirlos, si los terminos son iguales la resta será nula y la división nos mostrará un bonito error. La primera optimización que se observa no es demasiado significativa y con- siste tanto en la parte de pre-calculado de m1 y m2 como en la de re-calculado de m2, en calcular ESI y EDI paralelamente para aprovechar en la medida de lo posible el pipe-line del Pentium que consigue ejecutar varias instrucciones en un solo ciclo de reloj. Todo esto del pipe-line y otras optimizaciones poco significativas (a no ser que se esté en bucles críticos) como hacer XOR x,x en vez de MOV x,0 y todo eso lo explica Líyak en su sección de optimización de en- samblador en general, aquí estamos viendo un caso muy particular. La medida "mágica" que nos va a permitir augmentar la velocidad increiblemen- te es tan sencilla como cambiar en los bucles las instrucciones STOSB por sus equivalentes de 32bits: STOSD. Claro que aquí hay un problema, si movemos DWORDs en vez de BYTEs deberemos de mover una cantidad menor, exactamente una cuarta parte menos (he ahí la ganancia en velocidad), pero si divido entre 4 el resto puede ser hasta 3 bytes (pixels) que no se dibujaran. ¿Como solucionar esto para que no quede la linea a escalones? Pues dibujando los pixels que fal- tan con MOVSB o MOVSW; observa estos trozos de código equivalentes: Γ MOV CX, Longitud MOV CX, Longitud Γ REP STOSB SHR CX, 1 Γ JNC @@NoDoble1 Γ STOSB Γ @@NoDoble1: SHR CX, 1 Γ JNC @@NoDoble1b Γ STOSW Γ @@NoDoble1b:REP STOSd Podemos ver que el segundo fragmento es mucho más complicado que el primero, tiene 6 instrucciones más y 2 posibles saltos, pero pese a todo eso se gana en velocidad. Si en el primer desplazamiento de CX se produce carry (si el LSB o bit menos significativo estaba a 1), eso hará que se ejecute la instrucción STOSB que escribirá un solo pixel y luego lo mismo para el siguiente desplaza- miento con la instrucción STOSW que dibujará 2 pixels. La explicación de porque funciona es muy sencilla, en una división entre 4 (2^2) en binario, el resto son los 2 LSBs y el cociente el resto desplazado 2 posiciones a la derecha. Otro detalle más: con la instrucción STOSD no podiamos seguir dibujando los triangulos de izquierda y de derecha con la instrucción CLD y STD pues con esta segunda, cuando DI se ha de decrementar, primero pinta y luego decrementa con lo que el triangulo no se ajusta a lo esperado (puedes probarlo modificando el fichero 'TRIAN3.ASM' y lo observarás mejor). Se ha optado, pues, por incluir un pedazo de código automodificable que permitirá cambiar entre un par de NOPs y un SUB DI,CX para que se ajuste DI antes de dibujar los bytes. El módulo 'δTRIAN5.ASMπ' es el último paso en la implementación, el regreso a los origenes, la unión entre el Pascal y el assembler. Se ha creado un interfa- ce sencillo desde assembler para que TP llame a esa función y no lo haga direc- tamente a 'δFillTriangleπ'. Espero haber ilustrado un poco en la forma genérica de diseñar e implementar algoritmos en ensamblador gradualmente para los menos experimentados y una forma rápida de rellenar triangulos para quienes esten ha- ciendo su engine 3D o similar. ∞Navi/PhyMosys
